package org.example;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 3. 无重复字符的最长子串
 */
public class LengthOfLongestSubstring {

    public int lengthOfLongestSubstringOfficial(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int ans = 0;
        int rk = 0;
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            if(i!= 0){
                set.remove(s.charAt(i-1));
            }
            while (rk < s.length() && !set.contains(s.charAt(rk))) {
                set.add(s.charAt(rk));
                rk++;
            }
            ans = Math.max(ans, rk - i);
        }
        return ans;
    }

    /**
     * 自己实现
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int ans = 0;
        char[] charArray = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        int count = 0;
        for (int i = 0; i < charArray.length; i++) {
            boolean contains = map.containsKey(charArray[i]);
            if (contains) {
                count = 0;
                Integer existsIndex = map.get(charArray[i]);
                Set<Character> characters = map.keySet();
                Map<Character, Integer> mapNext = new HashMap<>();
                for (Character c : characters) {
                    if (map.get(c) > existsIndex) {
                        mapNext.put(c, map.get(c));
                        count++;
                    }
                }
                map = mapNext;
            }
            map.put(charArray[i], i);
            count++;
            if (count > ans) {
                ans = count;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
//        String s = "abcabcbb";
        String s = "pwwkew";
        LengthOfLongestSubstring lengthOfLongestSubstring = new LengthOfLongestSubstring();
        System.out.println(lengthOfLongestSubstring.lengthOfLongestSubstringOfficial(s));
    }
}
